Exchange systems implement exchange programs where participants in a transaction directly exchange resources or services for other resources or services without using a medium of exchange, such as money.
One example exchange system is a system implementing a kidney transplant exchange program. Kidney transplants allow patients with kidney diseases to replace their non-functional kidneys with healthy kidneys from deceased or, preferably, living donors. In many countries organ-selling is prohibited and illegal, so a living donor is usually closely-related to the patient. However, even if a patient is able to find a donor willing to donate his or her kidney, it is often the case that the kidney is not compatible to the patient's body. If an incompatible kidney is transplanted, the patient's body can reject the organ, leading to a failure of the transplant.
The compatibility of a donor kidney and patient can be tested and confirmed with a certain level of confidence prior to the transplant. Then, if a patient-donor pair is found to be incompatible or not well-matched, the pair can join a kidney exchange program to swap donor kidneys with another potential patient-donor pair. The kidney exchange program therefore enables the frequent issue of incompatibility in kidney transplant to be overcome by swapping kidneys between a group of patient-donor pairs.
The concept of kidney exchange was initially outlined in 1986 by Felix Rapaport, and the first kidney exchange program was operated in 1991 in South Korea. Since then, the idea has been gradually adopted and performed throughout different parts of the World. Today, many compatible patient-donor pairs join kidney exchange programs for the purpose of searching for even better-matched kidneys. In 2015, the largest recorded kidney exchange was performed, which involved 34 patient-donor pairs and 26 different hospitals over the course of three months.
Due to the increasing popularity of kidney exchange, the size of kidney exchange programs is constantly growing. As described in this specification, allocating the swap of kidneys in a kidney exchange system is a combinatorial optimization problem, and it is NP-complete when certain restrictions are enforced. Therefore, efficient algorithms are needed for solving the kidney exchange optimization problem. Due to the NP-completeness of the kidney exchange problem, there is no efficient algorithm for solving the problem on a classical computer.